package chapter4;

/**
 * 分治策略-矩阵乘法
 */
public class MatrixMultiply {

    public static int[][] squareMatrixMultiply(int[][] A, int[][] B) {
        int n = A.length;
        int[][] C = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        return C;
    }

    public static int[][] squareMatrixMultiplyRecursive2(int[][] A, int[][] B) {
        int l = A.length;
        int[][] C = new int[l][l];
        if (l == 1) {
            C[0][0] = A[0][0] * B[0][0];
            return C;
        }
        int left = 0;
        int right = l - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            C = squareMatrixMultiplyRecursive(A, B, C, mid);
        }
        return C;
    }

    public static int[][] squareMatrixMultiplyRecursive(int[][] A, int[][] B, int[][] C, int i) {
        int l = A.length;
        if (l == 1) {
            C[i][i] = A[i][i] * B[i][i];
            return C;
        }
        C[i][i] = A[i][i] * B[i][i] + A[i][i + 1] * B[i + 1][i];
        C[i][i + 1] = A[i][i] * B[i][i + 1] + A[i][i + 1] * B[i + 1][i + 1];
        C[i + 1][i] = A[i + 1][i] * B[i][i] + A[i + 1][i + 1] * B[i + 1][i];
        C[i + 1][i + 1] = A[i + 1][i] * B[i][i + 1] + A[i + 1][i + 1] * B[i + 1][i + 1];
        return C;
    }

}
